package Sort;

import java.util.Arrays;

/**
 * @Classname 堆排序
 * @Description TODO
 * @Date 2023/2/17 18:25
 * @Created by xjl
 */
public class 堆排序 {


    /**
     * @description: 构建大顶堆 并调整堆结构
     * @author: zhuangxiaoyan
     * @date: 2023/10/12 8:47
     * @param: [Array]
     * @return: void
     **/
    public static void heapSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        int n = array.length;
        //1.构建大顶堆 数组中最后的一个元素的父节点来构建整个堆树
        for (int i = (n / 2 - 1); i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(array, n, i);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素 从数组的最后的一个元素来调整
        for (int i = n - 1; i > 0; i--) {
            swap(array, i, 0);
            adjustHeap(array, i, 0);
        }
    }

    // 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
    // array 表示的数组的长度
    // length 表示数组的长度
    // i 表示的是数组节点的下标
    private static void adjustHeap(int[] array, int length, int i) {
        // 找到父节点和左右子节点中最大位置下标
        int largest = i;
        int lson = i * 2 + 1;
        int rson = i * 2 + 2;
        if (lson < length && array[largest] < array[lson]) {
            largest = lson;
        }
        if (rson < length && array[largest] < array[rson]) {
            largest = rson;
        }
        // 如果最大的下标不是当前，那就将当前的值与父节点进行交换，然后在调整新的位置的最大值,largest已经是新的最大位置的坐标。
        if (largest != i) {
            // 交换当前前的位置
            swap(array, largest, i);
            adjustHeap(array, length, largest);
        }
    }

    private static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    public static void main(String[] args) {
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }
}
